import copy
import regexp
from Queue import Queue
from collections import defaultdict

class _item_(object):
	
	def __init__(self, left, exp, pos, first):
		self.exp   = exp
		self.pos   = pos
		self.left  = left
		self.first = first
	
	def is_end(self):
		if len(self.exp) - 1 == self.pos: return True
		return False

	def is_same(self, item):
		if cmp(self.exp, item.exp) != 0: return False
		if item.left != self.left or item.pos != self.pos: return False
		if item.first != self.first: return False
		return True

	def is_similar(self, item):
		if cmp(self.exp, item.exp) != 0: return False
		if item.left != self.left or item.pos != self.pos: return False
		return True


class _item_set_(object):
	def __init__(self):
		self.items = []
		self.next = defaultdict( _item_set_ )

	def is_same(self, its):
		if len(its.items) != len(self.items): 
			return False
			
		vis = defaultdict(bool)
		for it in its.items:
			flag = False
			for i in range(len(self.items)):
				if vis[i] == False and it.is_same( self.items[i] ):
					vis[i] = True
					flag = True
					break
			if flag == False: return False
		return True
		

class grammer_praser(object):
	def __init__(self):
		self.exp = defaultdict(list)
		self.exp_id = defaultdict(int)
		self.items_id = defaultdict(int)
		self.terminal_set = set()
		self.non_terminal_set = set()
		self.grammer = defaultdict(list)
		self.first_set = defaultdict(set)
		self.infer_eps = defaultdict(int)
		self.degree_in  = defaultdict(int)
		self.degree_out = defaultdict(int)
		self.is_terminal = defaultdict(bool)

	def read_grammer(self):
		exp_id  = self.exp_id
		grammer = self.grammer
		degree_in = self.degree_in
		degree_out = self.degree_out
		count = -1
		with open('grammer.txt') as grammers:
			for line in grammers:
				line = line[:-2]
				line = line.strip()
				lis = line.split("=>")
				left = lis[0][1:-2]
				right = lis[1]
				lis = right.split('<')
				exp = []
				cur = left
				count += 1
				self.exp[str(count)] = []
				self.exp[str(count)].append(left)
				for item in lis :
					if item == ' ': continue
					exp.append(item[:-1])
					cur += item[:-1]
					self.exp[str(count)].append(item[:-1])
				exp_id[cur] = count
				grammer[left].append(exp)


		for left in grammer.keys():
			for exp in grammer[left]:
				degree_out[left] += 1
				for v in exp:
					degree_in[v]  += 1

		item_set = set()
		item_set.update( [node for node in degree_in] )
		item_set.update( [node for node in degree_out] )

		for item in item_set:
			if degree_in[item] != 0 and degree_out[item] == 0:
				self.terminal_set.add(item)
				self.is_terminal[item] = True
			else:
				self.non_terminal_set.add(item)
				self.is_terminal[item] = False
			degree_in[item]  = 0
			degree_out[item] = 0


	def get_infer_eps(self):

		grammer = self.grammer
		infer_eps = self.infer_eps
		terminal_set = self.terminal_set
		non_terminal_set = self.non_terminal_set

		for item in terminal_set:
			infer_eps[item] = 0

		infer_eps['eps'] = 1
 		for item in non_terminal_set:
 			infer_eps[item] = -1

 		while True:
	 		find = False
	 		for left in grammer.keys():
	 			if infer_eps[left] == 1: continue
	 			for exp in grammer[left]:
	 				flag = True
	 				for item in exp:
						if infer_eps[item] != 1: flag = False 
	 				if flag == True:
	 					find = True
	 					infer_eps[left] = 1
	 					break
	 		if find == False: break


	def get_first(self):

		self.get_infer_eps()
		grammer = self.grammer
		first_set = self.first_set
		infer_eps = self.infer_eps
		is_terminal = self.is_terminal
		terminal_set = self.terminal_set
		non_terminal_set = self.non_terminal_set
		degree_in = self.degree_in
		degree_out = self.degree_out

		graph = defaultdict(list)
		for cur in non_terminal_set:
			for exp in grammer[cur]:
				for item in exp:
					
					if item == 'eps': 
						continue

					if infer_eps[item]: 
						graph[item].append(cur)
						degree_out[item] += 1
						degree_in[cur] += 1
					elif is_terminal[item]:
						first_set[cur].add(item)
						break
					else:
						degree_out[item] += 1
						degree_in[cur] += 1
						graph[item].append(cur)
						break

		counter = 0
		number = len(non_terminal_set)
		while True:
			u = ' '
			for cur in non_terminal_set:
				if degree_in[cur] == 0:
					u = cur
			if u == ' ': break
			
			counter += 1
			degree_in[u] -= 1
			for v in graph[cur]:
				first_set[v].update( first_set[u] )
				degree_in[v] -= 1
			if counter == number: break

		for cur in non_terminal_set:
			if infer_eps[cur] == 1:
				first_set[cur].add('eps')
		for cur in terminal_set:
			first_set[cur].add(cur)
			# print cur
			# print first_set[cur]

	def cal_first(self, all_exp, pos,  exp, first = set()):
		first_set = self.first_set
		ret = set()
		flag = False
		for it in exp:
			if it == '$': continue
			if self.infer_eps[it] != 1:
				flag = True
			ret.update( first_set[it] )
			if flag: break

		if flag: return ret
		ret.update( first )
		return ret

	def closure(self, items):
		ret = [ ]
		queue = Queue()

		terminal_set = self.terminal_set
		for item in items:
			# print item
			queue.put( item )
			ret.append( item )

		while not queue.empty():
			u = queue.get()
			if u.exp[ u.pos ] == '$': continue
			if u.exp[ u.pos ] in terminal_set: continue

			next_first = self.cal_first( u.exp, u.pos, u.exp[u.pos+1:], u.first )
			for exp in self.grammer[ u.exp[ u.pos ] ]:
				item = _item_(u.exp[u.pos], exp, 0, next_first)
				has_vis = False
				for vis in ret:
					if vis.is_similar(item):
						has_vis = True
						vis.first.update( next_first )
				if has_vis == False:
					ret.append( item )
					queue.put( item )

		# print '====================================================='
		# for it in ret:
		# 	print it.exp
		# 	print it.first

		# print '====================================================='
		return ret


	def has_the_items(self, all_its, its):
		for it in all_its:
			if it.is_same(its): return it
		return None


	def constructor(self):
		grammer = self.grammer
		items_id = self.items_id

		self.get_first();
		self.first_set['$'] = '#'
		
		start = _item_set_()
		cur   = start

		it_pos  = 0
		it_left = 'start'
		it_exp  = grammer['start'][0]
		it_exp.append( '$' );
		it_first = self.first_set['$']
		it = _item_(it_left, it_exp, it_pos, it_first)
		cur.items.append( it )
		cur.items = self.closure( cur.items );

		queue = Queue()
		queue.put( cur )
		all_items = set()
		all_items.add( cur )

		
		count = 0
		items_id[cur] = count
		count += 1
		while not queue.empty():
			u = queue.get()
			vis = defaultdict(list)
			for item in u.items:
				rt = item.exp[ item.pos ]
				if rt == '$': continue
				if item.exp[-1] != '$': item.exp.append('$')
				vis[rt].append(_item_(item.left, item.exp, item.pos+1, item.first))

			for key in vis.keys():
				# print key
				its = _item_set_()
				its.items.extend( vis[key] )
				its.items = self.closure( its.items )
				rt = self.has_the_items( all_items, its )
				if rt == None:
					items_id[its] = count
					count += 1
					# print str(items_id[u]) + ' ' + key +' ' + str(items_id[its])
					queue.put(its)
					u.next[key] = its
					all_items.add(its) 
				else: 
					u.next[key] = rt

		return all_items
					# print str(items_id[u]) + ' ' + key +' ' + str(items_id[rt])
			# print '*********************************'
		# print count
		# for rt in all_items:
		# 	for z in rt.items:
		# 		print z.left
		# 		print z.exp
		# 		print z.pos
		# 		print z.first
		# 	print '----------------------'

	def exp_hash_key(self, left, exp):
		ret = left
		for it in exp:
			if it == '$': continue
			ret += it
		return ret

	def get_goto(self):

		table = []
		exp_id = self.exp_id
		items_id = self.items_id
		items_set = self.constructor()
		count = len(items_set) + 7
		while count > 0:
			table.append( defaultdict(dict) )
			count -= 1
		for items in items_set:
			u = items_id[items]
			for item in items.items:
				hash_key = self.exp_hash_key(item.left, item.exp)
				cur_exp_id = exp_id[hash_key]
				word = item.exp[ item.pos ]
				if word in items.next.keys():
					v = items_id[ items.next[word] ]
					if word in self.non_terminal_set:
						table[u][word] = str(v)
					else:
						table[u][word] = 'S' + str(v)
				
				for it in item.first:
					word = it
					if item.exp[ item.pos ] == '$':
						if item.left == 'start' and word == '#':
							table[u][word] = 'acc' 
						else:
							table[u][word] = 'r' + str(cur_exp_id)
							# print cur_exp_id
							# print hash_key

					elif word in items.next.keys():
						v = items_id[ items.next[word] ]
						if word in self.non_terminal_set:
							table[u][word] = str(v)
						else:
							table[u][word] = 'S' + str(v)

		for i in range( len(items_set) ):
			print str(i) + '  :  ' + str(table[i])
		return table

	def compiler(self, tokens):
		
		count = 1
		line = []
		table = self.get_goto()
		tokens.append([0,0,-1,0])
		for it in tokens:
			# print it
			# print it[2]
			# print count 
			# print '------------'
			if it[2] == count:
				line.append( it[1] )
			else:
				cur = []
				cur.append('#')
				# print line
				while len(line) != 0: 
					cur.append( line.pop() )

				state_stack = []
				symbol_stack = []
				action = []
				goto = []

				state_stack.append(0)
				symbol_stack.append('#')

				print cur
				while len(cur):
					# print 'cur           ' + str(cur)
					# print 'state_stack : ' + str(state_stack)
					# print 'symbol_stack: ' + str(symbol_stack)

					word = cur.pop()
					u  = state_stack.pop()
					# print 'word          ' + word
					# print 'cur_state     ' + str(u)
					# print table[u].keys()
					# print '---------------------------------------------------'
					if word not in table[u].keys():
						return False
					
					ac = table[u][word]
					
					if ac == 'acc':  break

					if ac[0] == 'S':
						# print 'S - > ' + ac[1:]
						state_stack.append(u)
						state_stack.append( int(ac[1:]) )
						symbol_stack.append(word)
					elif ac[0] == 'r':
						# print 'r - > ' + ac[1:]
						n = ac[1:]
						c = len(self.exp[n]) - 1
						symbol_stack.pop()
						while c > 1:
							symbol_stack.pop()
							state_stack.pop()
							c -= 1
						cur.append(word)
						cur.append(self.exp[n][0])
						symbol_stack.append(self.exp[n][0])

					else:	
						# print 'Goto ' + ac
						state_stack.append(u)
						state_stack.append( int(ac) )
						symbol_stack.append(word)

				if it[2] == -1 : 
					break
				line = []
				line.append(it[1])
				count += 1
				# print count
				# print it


		return True



if __name__ == '__main__':
	reg_dealer = regexp.Regexp()
	reg_dealer.regexp_to_dfa("lex_test.txt")
	regexp.lex("code.txt", reg_dealer)
	print '@ token list:'
	for item in regexp.tokens:
	    print item
	print	'\n'
	dealer = grammer_praser()
	dealer.read_grammer()
	if dealer.compiler(regexp.tokens) : 
		print ' grammer check done.'
	else:
		print ' grammer check error.'

 